package com.qch.edu.lagou.algorithm.dp;

/**
 * @Author qch
 * @Date 2021/7/23
 * 斐波那契数列
 * 递归分治+备忘录->动态规划
 * 空间换时间的方式
 *
 */
public class Fibber2 {
    //用于存储每次计算的结果
    static long[] sub=new long[100];
    public static long fib(int n)
    {
        if(n<=1)
            return n;
        //该数字已经被计算
        if(sub[n]!=0)
        {
            return sub[n];
        }
        else {
            sub[n]=fib(n-1)+fib(n-2);
        }
        return sub[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(64));
    }
}
